This invention relates to layout technique of wiring patterns or wiring routes in semiconductor integrated circuit devices such as gate arrays, standard cells, custom LSIs, and the like, and in wiring substrates.
Conventional methods that have been employed generally in automatic wiring design for semiconductor integrated circuit devices include a pattern limiting method, a maze routing method, a line search method and a channel assignment method as shown in FIG. 15 of the accompanying drawings.
The pattern limiting method makes connection between terminals in a predetermined pattern shape such as an L shape but its automatic wiring capability is low because available wiring patterns are limited. Therefore, this method can be applied to only rather simple wiring patterns.
The maze routing method is a method which controls wirability Of wirings on a wiring routing grid basis and searches a route from a start terminal to an end terminal by tracing wiring routing grids one by one in a predetermined direction. Since the search is made on a wiring routing grid basis in accordance with this maze routing method, its processing time increases and enormous work memory area is necessary for this search processing.
The line search method uses a line along a wiring routing grids as a unit of search and carries out the search while extending the lines in horizontal and vertical directions in such a manner as to bypass wiring inhibiting regions. Since the search is made on a line basis by this line search method, the processing time can be made shorter than in the maze routing method described above but there are inevitable limits to the reduction of the processing time and the work memory area.
The channel assignment method connects branches to a trunk on an inter-cell-column basis and can reduce the processing time but its handling is difficult for a chip model in which the wiring inhibiting regions are defined in a complicated manner. Moreover, this method cannot be applied easily to a multi-layer interconnection of three or more layers.
The logic scale of semiconductor integrated circuit devices is ever-increasing at present with a higher integration density and miniaturization of circuit elements in semiconductor integrated circuit devices and the demands for the reduction of the processing time and adaptability to multi-layered interconnection have been increasing in the automatic wiring processing. The following references can be cited as the prior art references relating to such demands.
(1) "Two-Layer Router Using Computational Geometric Means", (Data Processing Society, Design Automation 23-1, 19, Sep. 18, 1984) PA1 (2) "Updating Method of Wiring Pattern in Gridless Router", (Electronic Communication Society, CAS84-131, Dec. 1, 1984) PA1 (3) Japanese Patent Laid-Open No. 235683/1987
The methods described in the references (1) and (2) provide a two-layered wiring as an example, divide wirable regions on a chip into rectangles for each wiring layer, store a set of the sides of each divided rectangle as data, visualize graphically the crossing relations of the sides and determine the wiring route using the sides of the rectangles as the elements by making the search on this graph. For example, the wirable region in the first wiring layer shown in FIG. 16A is divided into rectangles and a graph is prepared by using the upper and lower sides a.about.l as the nodes (see FIG. 16D). The nodes on this graph are connected to one another by branch Only when the route using the second wiring layer exists between them. The wiring route extending from the start terminal S to the end terminal T is searched in accordance with this graph and its result is shown in FIG. 16C.
The method described in the reference (3) described above divides the wiring region and the wiring inhibiting region into rectangles and searches the route while changing dynamically the wiring sequence in accordance with the wiring regions and the shape of the net.
However, the studies conducted by the present inventor reveal that the following problems exist in the prior art technique described above. In accordance with the prior art technique of the references (1) and (2), the wiring route is searched by use of the sides of the rectangle as a unit. Accordingly, the wiring route is always bent at the edge of the wiring inhibiting region as shown in FIG. 16C. Therefore, the wiring route gets complicated and the number of through-holes increases, so that the yield of LSIs drops. For example, eight through-holes are necessary in the wiring route searched by this method as shown in FIG. 16C. However, there exists practically a wiring route having six through-holes as shown in FIG. 16E. In another example, there exists a wiring route RT2 having one through-hole and a wiring route RT1 having seven through-holes as shown in FIG. 16F. In such a case, a wiring route which minimizes the number of through-holes is employed preferably.
When the data necessary for the route search are stored in a graphic structure in a memory such as shown in FIG. 16D, the number of branches becomes enormous in a large-scale LSI and the memory capacity necessary for the work region of a computer becomes so great as to exceed the practical operational limit. Assuming, for example, an LSI having a memory capacity of 4 bytes for one branch, 200 branches for one node and a 100K gate scale, and assuming also that the number of nodes necessary for the LSI as a whole is 1000K; then, the memory capacity of the memory necessary for the work region becomes 800M bytes and this value by far exceeds the practical value.
In view of these problems, the prior art technique described in the reference (3) will not provide any technique exceeding the concept that the wiring route is searched by utilizing the rectangles.